COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a15.tex[106,phy] \today\hfill}

\bigskip
\line{\bf [Subjects: Programming Methodology, Invariants.]\hfill}

\bigskip
Suppose I am reading a numerical formula, like ``$13+273\times 8/47-$,''
etc. When I~have seen ``$13+273\times 8$'', there is nothing I~can yet
do to evaluate the formula; the ``$+$'' must wait for the~``$\times$'',
and the ``$273\times 8$'' might be followed by another digit.  When
I~see the division sign, though, I~know that I~need look no further;
I~can multiply 273 by~8, giving~2184, and simplify what I~have seen
to``$13+2184/$''.

In the absence of parentheses, in fact, I~can always compress the part
of the formula I~have seen to no more than five symbols, each of them
a number or one of the operators $+\,$, $-\,$, $\times\,$,~$/$.

Let's suppose I~have read a partial formula
$$A\oplus B\;\otimes$$
where $A$ and $B$ are numbers, $\oplus$ is either $+$ or~$-\,$, and
$\otimes$ is either $\ast$ or~$/$. I~now read another number,~$C$,
and another operator,~$\odot$.

How can I compress the six symbols
$$A\oplus B\otimes C\;\odot$$
down to the original four?

\smallskip
\disleft 25pt:(1):
If $\odot$ is $\ast$ or $/$, it suffices to set $D=B\odot C$, and compress
to $A\oplus D\;\odot$.

\smallskip
\disleft 25pt:(2):
If $\odot$ is $+$ or $-\,$, we can set $D=B\otimes C$, 
giving $A\oplus D\;\odot$,
and then set $E=A\oplus D$, giving $E\;\odot$.
This is too compressed; making it $E\odot 1\,\ast$, though, gets back to
exactly four symbols, and each operator is one of the same kinds we
originally assumed.

\smallskip
\disleft 25pt:(3):
If $\odot$ is not an operator but a sentinel to mark the end of the formula,
we can finish up by evaluating $D=B\otimes C$, $E=A\oplus D$, and
printing~$E$.

At this point, I know how to keep the algorithm going once started, and how
to finish it. How can I~start it? The input does not necessarily have
$+$ or~$-$ as the first operation and $\ast$ or $/$ as the second.

\vfill\eject

\disleft 255pt::
Professor having idea.
\disleft 255pt::
Occurs at least once per year.

\vskip 2.5in

\noindent If it's not already like that, {\sl make it like that\/}. Put
``$0+1\,\ast$'' in front of the formula. The zero, added to what follows,
won't change anything; the~1, multiplied by part of what follows, won't either.

Using $X1$, $X2$, and $X3$ as variables to hold $\oplus\,$, $\otimes\,$, and
$\odot$ respectively, the algorithm is now:

\smallskip
\halign{\qquad\lft{\tt #}\cr
(* Include declaration of procedure VALUE *)\cr
(* Initialize *)\cr
A:=0; X1:=`+';\cr
B:=1; X2:=`*';\cr
READ(C); READ(X3) (* A+B*C. *)\cr
WHILE X3 is not a sentinel DO\cr
(* Main iteration *)\cr
\qq BEGIN\cr
\qq D:=VALUE(B,X2,C);\cr
\qq IF (X3='+') OR (X3='-') THEN\cr
\qq\qq\qq BEGIN\cr
\qq\qq\qq A:=VALUE(A,X1,D);\cr
\qq\qq\qq X1:=X3;\cr
\qq\qq\qq B:=1;\cr
\qq\qq\qq X2:='*'\cr
\qq\qq\qq END\cr
\qq ELSE\cr
\qq\qq\qq BEGIN\cr
\qq\qq\qq B:=D;\cr
\qq\qq\qq X2:=X3\cr
\qq\qq\qq END\cr
\qq END\cr
(* A+B*C followed by sentinel *)\cr
D:=VALUE(B,X2,C);\cr
WRITE(VALUE(A,X1,D))\cr}

\smallskip
To make this algorithm workable, I had to find an invariant:

\smallskip
\display 40pt:: The formula in hand is $A\oplus B\;\otimes$, where $\oplus$
is $+$ or $-$ and $\otimes$ is $\ast$ or~$/$. 

\smallskip\noindent
Had the invariant been too restrictive, like

\smallskip
\display 40pt:: The formula in hand is $A\;\odot$,

\smallskip\noindent
reading a formula like $12+345\,\ast\ldots$ would leave me unable to get
the formula into the specified form. Had the invariant been too permissive,
like

\smallskip
\display 40pt:: The formula in hand is a sequence of number, operator, number,
operator, $\ldots\,$, number, operator,

\smallskip\noindent
I would have to provide for far more cases than the three that the actual
algorithm handles. I~picked the invariant just permissive enough that 
I~could stay within it, once started. When I~get around to thinking of
initialization, the invariant requires a $+$ or~$-\,$, and
a $\ast$ or $/$: the formula does not necessarily contain either, so I~must
provide them myself to start the algorithm right.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\bye